# Problem 10
# The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
# Find the sum of all the primes below two million.

import unittest
import math
import Utility


def getSumOfPrimes(N):
    sum = 0
    for i in getPrimesInRange(N):
            sum += i
    return sum;

    
def getPrimesInRange(N):
    sieve = [True] * (N + 1)
    N_root = int(math.sqrt(N))
    for i in range(2, N_root + 1):
        if sieve[i] == True:
            j = 2
            k = j * i
            while k <= N:
                sieve[k] = False
                j += 1
                k = j * i    
    result = []
    for i in range(2, N + 1):
        if sieve[i] == True:
            result.append(i)
    return result    
    

def getPrimesInRange_2(N):
    sieve = [True] * (N + 1)
    N_root = int(math.sqrt(N))
    for i in range(2, N_root + 1):
        if sieve[i] == True:
            for j in range(i + 1, N + 1):
                if j % i == 0:
                    sieve[j] = False
    result = []
    for i in range(2, N + 1):
        if sieve[i] == True:
            result.append(i)
    return result

    
def getPrimesInRange_1(N):
    result = []
    for i in range(2, N + 1):
        if Utility.isPrime(i):
            result.append(i)
    return result
    
    
class TestP010(unittest.TestCase):
    def test_getSumOfPrimes(self):
        self.assertEqual(getPrimesInRange(2), [2])
        self.assertEqual(getPrimesInRange(3), [2, 3])
        self.assertEqual(getPrimesInRange(7), [2, 3, 5])
        self.assertEqual(getSumOfPrimes(10), 17)
        self.assertEqual(getSumOfPrimes(20), 77)
        #self.assertEqual(getSumOfPrimes(2000000), 142913828922) # 1st 34.312s; 2nd 43.827s; 3rd 0.984
        
        
        


if __name__ == '__main__':
    P010 = unittest.TestLoader().loadTestsFromTestCase(TestP010)
    unittest.TextTestRunner(verbosity=2).run(P010)
    #print "the sum of all the primes below two million is [%d]" % getSumOfPrimes(2000000)